LC174. 地下城游戏

1. 题目

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格 。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健 康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整 数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意： 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房 间以及公主被监禁的右下角房间。

示例 1：

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。

示例 2：

输入：dungeon = [[0]]
输出：1

提示：

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

2. 思路

• 如果从 (0, 0) 位置出发，会发现 dp[i][j] 难以定义
• 不妨从 公主所在位置出发， 将 dp[i][j] 定义为：从 (i, j) 位置到公主所在为止的最小起始值。
• 实际上，可以将公主所在位置看成下图当中的红色部分

---

• 在动态规划过程当中，dp 数组的大小是 (row + 1) * (col + 1)
• 因为公主位置需要在 dungeon[row - 1][col - 1] 再往下走一步
• 那么， dp[row - 1][col] == dp[row][col - 1] == 1，因为一旦到 0 就无法移动了，所以这个位置至少是 1
• 状态转移方程

$$\begin{array}{rl}minCost=& min(dp[i+1][j],dp[i][j+1])\\ dp[i][j]=& max(1,minCost-dungeon[i][j])\end{array}$$

• 其中， minCost - dungeon[i][j] 可以看成从 (i, j) 位置到下一个位置的最小消耗，相当于 minCost = dp[i][j] + dungon[i][j] 。但是，一旦 minCost - dungeon[i][j] 小于 1 , 该位置作为起始值，至少需要为 1。

---

• 此题还有记忆化搜索的方法去解决

3. 代码

func maxx(a int, b int) int {
	if a > b {
		return a
	}

	return b
}

func minn(a int, b int) int {
	if a < b {
		return a
	}

	return b
}

func calculateMinimumHP(dungeon [][]int) (ans int) {
	row := len(dungeon)
	col := len(dungeon[0])

	dp := make([][]int, row+1)
	for i := 0; i < row+1; i++ {
		dp[i] = make([]int, col+1)
		for j := 0; j < col+1; j++ {
			dp[i][j] = math.MaxInt32
		}
	}

	// 此处可以看成公主真正的位置,也是 dp 的出发点
	// 出发点必须是1, 因为一旦到达0就无法进行下一步行动了
	// dp[i][j] 可以看成到 "公主" 位置所需要的最小值
	dp[row][col-1], dp[row-1][col] = 1, 1
	for i := row - 1; i >= 0; i-- {
		for j := col - 1; j >= 0; j-- {
			minCost := minn(dp[i][j+1], dp[i+1][j])
			dp[i][j] = maxx(minCost-dungeon[i][j], 1)
		}
	}

	return dp[0][0]
}